package leet977sortsquare

func SortSquares(nums []int) []int {
	n := len(nums)
	// 最终的数组肯定是和nums一样长的，所以直接make出定长的数组即可。
	result := make([]int, n)
	// 双指针法，左指针指向数组的开头，右指针指向数组的结尾
	// 因为数组是有序的，那么两边的平方值一定是比中间的平方值要大，所以我们从两边比较着向中间靠拢...
	left, right := 0, n-1
	// 因为我们是从大到小在获取得到平方值，所以此处的i我们从n-1,也就是数组尾部开始填充
	for i := n - 1; i >= 0; i-- {
		// 取两侧中较大绝对值的数的平方，然后用完之后移动指针（移动规则是左指针右移，右指针左移
		if abs(nums[left]) > abs(nums[right]) {
			result[i] = nums[left] * nums[left]
			left++
		} else {
			result[i] = nums[right] * nums[right]
			right--
		}
	}
	return result
}
func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}
